//
// Created by weslywang on 2020/4/25.
//

#include "common.h"

// 按层遍历树
vector<vector<int>> levelOrder(TreeNode *root) {
    queue<TreeNode *> qu;
    vector<vector<int>> result;
    vector<int> row;
    TreeNode *pos = root, *front, *pre;
    if (root)
        qu.push(root);
    pre = root;
    while (!qu.empty()) {
        front = qu.front();
        row.push_back(front->val);
        qu.pop();
        if (front == pos) {
            result.push_back(row);
            row.clear();
            if (front->left) {
                qu.push(front->left);
                pos = front->left;
            }
            if (front->right) {
                qu.push(front->right);
                pos = front->right;
            }
            if (!front->left && !front->right)
                pos = pre;
        } else {
            if (front->left) {
                qu.push(front->left);
                pre = front->left;
            }
            if (front->right) {
                qu.push(front->right);
                pre = front->right;
            }
        }
    }
    return result;
}

void Common::makeTreeFull(TreeNode *root) {
    if (!root) {
        return;
    }
    int height = getTreeHeight(root);
    cout << "树高：" << height << endl;
    queue<TreeNode *> qu;
    vector<vector<int>> result;
    vector<int> row;
    int currentLevel = 1;//当前遍历的层
    TreeNode *pos = root, *front, *pre;
    if (root) {
        qu.push(root);
    }
    while (!qu.empty()) {
        front = qu.front();
        row.push_back(front->val);
        qu.pop();
        if (front == pos) {
            result.push_back(row);
            row.clear();
            currentLevel++;
        }
        if (!front->left && currentLevel < height) {
            front->left = new TreeNode(defaultEmptyTreeNodeVal);
        }
        if (front->left) {
            qu.push(front->left);
        }
        if (!front->right && currentLevel < height) {
            front->right = new TreeNode(defaultEmptyTreeNodeVal);
        }
        if (front->right) {
            qu.push(front->right);
        }
        if (front == pos) {
            pos = front->right;
        }
    }
}


int Common::getTreeHeight(TreeNode *tree) {
    int height = 0;
    if (!tree) {
        return 0;
    }
    if (!tree->left && !tree->right) {
        return 1;
    }
    height = 1 + max(getTreeHeight(tree->left), getTreeHeight(tree->right));
    return height;
}

void Common::printTree(TreeNode *tree) {
    makeTreeFull(tree);
    vector<vector<int>> data = levelOrder(tree);
    cout << setiosflags(ios::left | ios::showpoint);
    int offset = 0, pace = 4;
    string empty = "                                                  ";
    for (int i = 0; i < data.size(); i++) {
        offset = (data.size() - 1 - i) * pace;
        cout << empty.substr(0, offset);
        for (int k = 0; k < data[i].size(); k++) {
            if (data[i][k] == defaultEmptyTreeNodeVal) {
                cout << setw(pace) << "";
            } else {
                cout << setw(pace) << data[i][k];
            }
        }

        cout << endl;
    }

}

vector<vector<int>> Common::loadData() {
    FILE *fp;
    vector<vector<int>> result;
    int tmp;
    char ch;
    fp = freopen("/Users/wangshuai/project/C/LeetCode2020/data/data.txt", "r", stdin);
    if (fp != NULL) {
        vector<int> row;
        while (fscanf(fp, "%d%c", &tmp, &ch) != EOF) {
            row.push_back(tmp);
            if (ch == '\n') {
                result.push_back(row);
                row.clear();
            }
        }
        if (row.size() > 0) {
            result.push_back(row);
        }
    }
    return result;
}

vector<vector<string>> Common::loadStringData() {
    FILE *fp;
    vector<vector<string>> result;
    char tmp[100];
    char ch;
    fp = freopen("/Users/wangshuai/project/C/LeetCode2020/data/data.txt", "r", stdin);
    if (fp != NULL) {
        vector<string> row;
        while (fscanf(fp, "%s%c", &tmp, &ch) != EOF) {
            row.push_back(tmp);
            if (ch == '\n') {
                result.push_back(row);
                row.clear();
            }
        }
        if (row.size() > 0) {
            result.push_back(row);
        }
    }
    return result;
}

vector<string> Common::loadStringData2() {
    FILE *fp;
    vector<string> result;
    char tmp[2000];
    fp = freopen("/Users/wangshuai/project/C/LeetCode2020/data/data.txt", "r", stdin);
    if (fp != NULL) {
        while (fscanf(fp, "%s", &tmp) != EOF) {
            result.push_back(tmp);
        }
    }
    return result;
}

void Common::printVector(vector<vector<string> > &list) {
    for (int i = 0; i < list.size(); i++) {
        for (int k = 0; k < list[i].size(); k++) {
            if (k > 0) {
                cout << " ";
            }
            cout << list[i][k];
        }
        cout << endl;
    }
}

void Common::printVector(vector<vector<int> > &list) {
    for (int i = 0; i < list.size(); i++) {
        for (int k = 0; k < list[i].size(); k++) {
            if (k > 0) {
                cout << " ";
            }
            cout << list[i][k];
        }
        cout << endl;
    }
}

void Common::printVector(vector<vector<char> > &list) {
    for (int i = 0; i < list.size(); i++) {
        for (int k = 0; k < list[i].size(); k++) {
            if (k > 0) {
                cout << " ";
            }
            cout << list[i][k];
        }
        cout << endl;
    }
}

vector<vector<char>> Common::loadCharData() {
    FILE *fp;
    vector<vector<char>> result;
    char ch1, ch2;
    fp = freopen("/Users/wangshuai/project/C/LeetCode2020/data/data.txt", "r", stdin);
    if (fp != NULL) {
        vector<char> row;
        while (fscanf(fp, "%c%c", &ch1, &ch2) != EOF) {
            row.push_back(ch1);
            if (ch2 == '\n') {
                result.push_back(row);
                row.clear();
            }
        }
        if (row.size() > 0) {
            result.push_back(row);
        }
    }
    return result;
}

TreeNode *Common::makeTree(vector<int> num) {
    if (num.size() < 1) {
        return NULL;
    }
    TreeNode *root = new TreeNode(num[0]), *tmp, *front;
    queue<TreeNode *> qu;
    qu.push(root);
    bool flag = true;
    int maxInt = INT_MAX;
    front = qu.front();
    qu.pop();
    for (int i = 1; i < num.size(); i++) {
        if (num[i] != maxInt) {
            if (flag) {
                tmp = new TreeNode(num[i]);
                qu.push(tmp);
                front->left = tmp;
                flag = false;
            } else {
                tmp = new TreeNode(num[i]);
                qu.push(tmp);
                front->right = tmp;
                flag = true;
                front = qu.front();
                qu.pop();
            }
        } else {
            if (flag) {
                flag = false;
            } else {
                flag = true;
                front = qu.front();
                qu.pop();
            }
        }
    }
    return root;
}

Node *Common::treeNodeToNode(TreeNode *tree) {
    if (!tree) {
        return NULL;
    }
    Node *node = new Node(tree->val);
    node->left = treeNodeToNode(tree->left);
    node->right = treeNodeToNode(tree->right);
    return node;
}